package com.company.TreeNodeLK;

import java.util.*;

public class TreeTest {

    public static void main(String[] args) {
        int[] arr = {30,15,6,20,40,35,50};
        TreeNode node  = insert(arr);
        System.out.println(qian(node));
        System.out.println(hou(node));
        System.out.println(cengci(node));
        System.out.println(select(node,13));

    }
    //构建二叉树
    public static TreeNode insert(int[] arr){
        TreeNode node = new TreeNode(arr[0]);
        for(int i=1;i<arr.length;i++){
            TreeNode temp = node;
            while(true){
                if(arr[i]>temp.val){
                    if(temp.right==null){
                        temp.right = new TreeNode(arr[i]);
                        break;
                    }else{
                        temp = temp.right;
                    }
                }else{
                   if(temp.left==null){
                       temp.left = new TreeNode(arr[i]);
                        break;
                   }else{
                       temp = temp.left;
                   }
                }
            }
        }
        return node;
    }
    public static boolean select(TreeNode node,int val){
        TreeNode temp = node;
        while(temp!=null){
            if(val>temp.val){
                temp = temp.right;
            }else if(val<temp.val){
                temp = temp.left;
            }else if(temp.val==val){
                return true;
            }
        }


        return false;
    }

    //前中后遍历
    public static List<Integer> qian(TreeNode node){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            } else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return list;
    }


    public static List<Integer> zhong(TreeNode node){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }

    public static List<Integer> hou(TreeNode node){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
    //层次bianli
    public static List<Integer> cengci(TreeNode node){
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(node);
        while(!deque.isEmpty()){
            int n = deque.size();
            for(int i=0;i<n;i++){
                TreeNode temp = deque.removeFirst();
                if(temp.left!=null){
                    deque.add(temp.left);
                }
                if(temp.right!=null){
                    deque.add(temp.right);
                }
                list.add(temp.val);
            }
        }
        return list;
    }


}
